home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 10 / AACD 10.iso / AACD / Online / SpeakFreely / src / idea / idea.c < prev    next >
C/C++ Source or Header  |  2000-05-18  |  17KB  |  541 lines
  1. /* idea.c - C source code for IDEA block cipher. IDEA (International Data 
  2.  * Encryption Algorithm), formerly known as IPES (Improved Proposed Encryption
  3.  * Standard). Algorithm developed by Xuejia Lai and James L. Massey, of ETH 
  4.  * Zurich. This implementation modified and derived from original C code 
  5.  * developed by Xuejia Lai. Zero-based indexing added, names changed from IPES
  6.  * to IDEA. CFB functions added. Random number routines added. Optimized for 
  7.  * speed 21 Oct 92 by Colin Plumb <colin@nsq.gts.org>. This code assumes that 
  8.  * each pair of 8-bit bytes comprising a 16-bit word in the key and in the 
  9.  * cipher block are externally represented with the Most Significant Byte 
  10.  * (MSB) first, regardless of internal native byte order of the target CPU.  */
  11.  
  12. #include "idea.h"
  13.  
  14. #define min(x, y) (((x) < (y)) ? (x) : (y))
  15.  
  16. #ifdef TEST
  17. #include <stdio.h>
  18. #include <time.h>
  19. #endif
  20.  
  21. #ifdef sgi
  22. #define HIGHFIRST
  23. #endif
  24.  
  25. #ifdef sun
  26. #define HIGHFIRST
  27. #define const
  28. #endif
  29.  
  30. #define TRUE    1
  31. #define FALSE    0
  32.  
  33. #define IDEABLOCKSIZE 8
  34. #define ROUNDS      8               /* Don't change this value, should be 8 */
  35. #define KEYLEN        (6*ROUNDS+4)    /* length of key schedule */
  36.  
  37. #define byte    unsigned char
  38. #define word16    unsigned short
  39. #define boolean int
  40. #define word32    unsigned long
  41. #define byteptr unsigned char *
  42.  
  43. typedef word16 IDEAkey[KEYLEN];
  44.  
  45. #ifdef IDEA32 /* Use >16-bit temporaries */
  46. #define low16(x) ((x) & 0xFFFF)
  47. typedef unsigned int uint16;        /* at LEAST 16 bits, maybe more */
  48. #else
  49. #define low16(x) (x)                /* this is only ever applied to uint16's */
  50. typedef word16 uint16;
  51. #endif
  52.  
  53. #ifdef _GNUC_
  54. /* __const__ simply means there are no side effects for this function,
  55.  * which is useful info for the gcc optimizer */
  56. #define CONST __const__
  57. #else
  58. #define CONST
  59. #endif
  60.  
  61. static void en_key_idea();
  62. static void de_key_idea();
  63. static void cipher_idea();
  64.  
  65. /* Multiplication, modulo (2**16)+1. Note that this code is structured like 
  66.  * this on the assumption that untaken branches are cheaper than taken 
  67.  * branches, and the compiler doesn't schedule branches. */
  68.  
  69. #ifdef SMALL_CACHE
  70. CONST static uint16 mul(register uint16 a, register uint16 b)
  71. {
  72.        register word32 p;
  73.        if (a)
  74.        {     if (b)
  75.          {        p = (word32)a * b;
  76.             b = low16(p);
  77.             a = p>>16;
  78.             return b - a + (b < a);
  79.          }
  80.          else
  81.          {        return 1-a;
  82.          }
  83.        }
  84.        else
  85.        {     return 1-b;
  86.        }
  87. }
  88. #endif /* SMALL_CACHE */
  89.  
  90. /* Compute multiplicative inverse of x, modulo (2**16)+1, using Euclid's GCD 
  91.  * algorithm. It is unrolled twice to avoid swapping the meaning of the 
  92.  * registers each iteration; some subtracts of t have been changed to adds.  */
  93.  
  94. CONST static uint16 inv(x)     
  95.     uint16 x;
  96. {
  97.        uint16 t0, t1;
  98.        uint16 q, y;
  99.        if (x <= 1)
  100.          return x;      /* 0 and 1 are self-inverse */
  101.        t1 = 0x10001 / x;  /* Since x >= 2, this fits into 16 bits */
  102.        y = 0x10001 % x;
  103.        if (y == 1)
  104.          return low16(1-t1);
  105.        t0 = 1;
  106.        do
  107.        {     q = x / y;
  108.          x = x % y;
  109.          t0 += q * t1;
  110.          if (x == 1)
  111.             return t0;
  112.          q = y / x;
  113.          y = y % x;
  114.          t1 += q * t0;
  115.        } while (y != 1);
  116.        return low16(1-t1);
  117. }
  118.  
  119. /*     Compute IDEA encryption subkeys Z */
  120.  
  121. static void en_key_idea(userkey, Z)
  122.     word16 *userkey; word16 *Z;
  123. {
  124.        int i,j;
  125.        /* shifts */
  126.        for (j=0; j<8; j++)
  127.          Z[j] = *userkey++;
  128.        for (i=0; j<KEYLEN; j++)
  129.        {     i++;
  130.          Z[i+7] = Z[i & 7] << 9 | Z[i+1 & 7] >> 7;
  131.          Z += i & 8;
  132.          i &= 7;
  133.        }
  134. }
  135.  
  136. /*     Compute IDEA decryption subkeys DK from encryption subkeys Z */
  137. /* Note: these buffers *may* overlap! */
  138.  
  139. static void de_key_idea(Z, DK)
  140.     IDEAkey Z; IDEAkey DK;
  141. {
  142.        int j;
  143.        uint16 t1, t2, t3;
  144.        IDEAkey T;
  145.        word16 *p = T + KEYLEN;
  146.        t1 = inv(*Z++);
  147.        t2 = -*Z++;
  148.        t3 = -*Z++;
  149.        *--p = inv(*Z++);
  150.        *--p = t3;
  151.        *--p = t2;
  152.        *--p = t1;
  153.        for (j = 1; j < ROUNDS; j++)
  154.        {
  155.          t1 = *Z++;
  156.          *--p = *Z++;
  157.          *--p = t1;
  158.          t1 = inv(*Z++);
  159.          t2 = -*Z++;
  160.          t3 = -*Z++;
  161.          *--p = inv(*Z++);
  162.          *--p = t2;
  163.          *--p = t3;
  164.          *--p = t1;
  165.        }
  166.        t1 = *Z++;
  167.        *--p = *Z++;
  168.        *--p = t1;
  169.        t1 = inv(*Z++);
  170.        t2 = -*Z++;
  171.        t3 = -*Z++;
  172.        *--p = inv(*Z++);
  173.        *--p = t3;
  174.        *--p = t2;
  175.        *--p = t1;
  176. /* Copy and destroy temp copy */
  177.        for (j = 0, p = T; j < KEYLEN; j++)
  178.        {
  179.          *DK++ = *p;
  180.          *p++ = 0;
  181.        }
  182. }
  183.  
  184. /* MUL(x,y) computes x = x*y, modulo 0x10001. Requires two temps, t16 and t32.
  185.  * x must me a side-effect-free lvalue. y may be anything, but unlike x, must 
  186.  * be strictly 16 bits even if low16() is #defined. All of these are 
  187.  * equivalent; see which is faster on your machine.  */
  188.  
  189. #ifdef SMALL_CACHE
  190. #define MUL(x,y) (x = mul(low16(x),y))
  191. #else
  192. #ifdef AVOID_JUMPS
  193. #define MUL(x,y) (x = low16(x-1), t16 = low16((y)-1), \
  194.              t32 = (word32)x*t16+x+t16+1, x = low16(t32), \
  195.          t16 = t32>>16, x = x-t16+(x<t16) )
  196. #else
  197. #define MUL(x,y) ((t16 = (y)) ? (x=low16(x)) ? \
  198.         t32 = (word32)x*t16, x = low16(t32), t16 = t32>>16, \
  199.         x = x-t16+(x<t16) : \
  200.     (x = 1-t16) : (x = 1-x))
  201. #endif
  202. #endif
  203.  
  204. /* IDEA encryption/decryption algorithm . In/out can be the same buffer */ 
  205.  
  206. static void cipher_idea(in, out, Z)
  207.     word16 in[4]; word16 out[4]; register CONST IDEAkey Z;
  208. {
  209.        register uint16 x1, x2, x3, x4, t1, t2;
  210.        register uint16 t16;
  211.        register word32 t32;
  212.        int r = ROUNDS;
  213.        x1 = *in++;  x2 = *in++;
  214.        x3 = *in++;  x4 = *in;
  215.        do
  216.        {
  217.          MUL(x1,*Z++);
  218.          x2 += *Z++;
  219.          x3 += *Z++;
  220.          MUL(x4, *Z++);
  221.          t2 = x1^x3;
  222.          MUL(t2, *Z++);
  223.          t1 = t2 + (x2^x4);
  224.          MUL(t1, *Z++);
  225.          t2 = t1+t2;
  226.          x1 ^= t1;
  227.          x4 ^= t2; 
  228.          t2 ^= x2;
  229.          x2 = x3^t1;
  230.          x3 = t2;
  231.        } while (--r);
  232.        MUL(x1, *Z++);
  233.        *out++ = x1;
  234.        *out++ = x3 + *Z++;
  235.        *out++ = x2 + *Z++;
  236.        MUL(x4, *Z);
  237.        *out = x4;
  238. }
  239.  
  240. #ifdef TEST
  241.  
  242. /* Number of Kbytes of test data to encrypt. Defaults to 1 MByte. */
  243.  
  244. #ifndef KBYTES
  245. #define KBYTES 1024
  246. #endif
  247.  
  248. #ifndef CLOCKS_PER_SEC
  249. #define CLOCKS_PER_SEC 1000000
  250. #endif
  251.  
  252. int main()
  253. {      /* Test driver for IDEA cipher */ 
  254.        int i, j, k; 
  255.        IDEAkey Z, DK;
  256.        word16 XX[4], TT[4], YY[4];     
  257.        word16 userkey[8];
  258.        clock_t start, end;
  259.        long l;
  260.  
  261.        /* Make a sample user key for testing... */
  262.  
  263.        for(i=0; i<8; i++)
  264.          userkey[i] = i+1;
  265.  
  266.        /* Compute encryption subkeys from user key... */
  267.  
  268.        en_key_idea(userkey,Z);
  269.        printf("\nEncryption key subblocks: ");
  270.        for(j=0; j<ROUNDS+1; j++)
  271.        {
  272.              printf("\nround %d:   ", j+1);
  273.          if (j==ROUNDS)
  274.             for(i=0; i<4; i++)
  275.                           printf(" %6u", Z[j*6+i]);
  276.          else
  277.             for(i=0; i<6; i++)
  278.                           printf(" %6u", Z[j*6+i]);
  279.        }
  280.  
  281.        /* Compute decryption subkeys from encryption subkeys... */
  282.  
  283.        de_key_idea(Z,DK);
  284.        printf("\nDecryption key subblocks: ");
  285.        for(j=0; j<ROUNDS+1; j++)
  286.        {
  287.              printf("\nround %d:   ", j+1);
  288.          if (j==ROUNDS)
  289.             for(i=0; i<4; i++)
  290.                           printf(" %6u", DK[j*6+i]);
  291.          else
  292.             for(i=0; i<6; i++)
  293.                           printf(" %6u", DK[j*6+i]);
  294.        }
  295.  
  296.        /* Make a sample plaintext pattern for testing... */
  297.  
  298.        for (k=0; k<4; k++)
  299.          XX[k] = k;
  300.        printf("\n Encrypting %d KBytes (%ld blocks)...", KBYTES, KBYTES*64l);
  301.        fflush(stdout);
  302.        start = clock();
  303.        cipher_idea(XX,YY,Z);         /* encrypt plaintext XX, making YY */ 
  304.        for (l = 1; l < 64*KBYTES; l++)
  305.          cipher_idea(YY,YY,Z);   /* repeated encryption */
  306.        cipher_idea(YY,TT,DK);         /* decrypt ciphertext YY, making TT */ 
  307.        for (l = 1; l < 64*KBYTES; l++)
  308.          cipher_idea(TT,TT,DK);  /* repeated decryption */
  309.        end = clock() - start;
  310.        l = end * 1000. / CLOCKS_PER_SEC + 1;
  311.        i = l/1000;
  312.        j = l%1000;
  313.        l = KBYTES * 1024. * CLOCKS_PER_SEC / end;
  314.  
  315.        printf("%d.%03d seconds = %ld bytes per second\n", i, j, l);
  316.        printf("\nX %6u   %6u  %6u  %6u \n",    
  317.      XX[0], XX[1],    XX[2], XX[3]);
  318.        printf("Y %6u   %6u  %6u  %6u \n",
  319.      YY[0], YY[1],    YY[2], YY[3]);
  320.        printf("T %6u   %6u  %6u  %6u \n",
  321.      TT[0], TT[1],    TT[2], TT[3]);
  322.        /* Now decrypted TT should be same as original XX */
  323.        for (k=0; k<4; k++)
  324.          if (TT[k] != XX[k])
  325.          {
  326.                     printf("\n\07Error!  Noninvertable encryption.\n");
  327.             exit(-1);       /* error exit */ 
  328.          }
  329.        printf("\nNormal exit.\n");
  330.        return 0;
  331. }
  332. #endif /* TEST */
  333.  
  334. /* xorbuf - change buffer via xor with random mask block. Used for Cipher 
  335.  * Feedback (CFB) or Cipher Block Chaining (CBC) modes of encryption. Can be
  336.  *  applied for any block encryption algorithm, with any block size, such as 
  337.  * the DES or the IDEA cipher.    */
  338.  
  339. static void xorbuf(buf, mask, count)
  340.     register byteptr buf; register byteptr mask; register int count;
  341. /*     count must be > 0 */
  342. {
  343.        if (count) 
  344.          do
  345.             *buf++ ^= *mask++;
  346.          while (--count);
  347. }      /* xorbuf */
  348.  
  349. /* cfbshift - shift bytes into IV for CFB input. Used only for Cipher Feedback
  350.  * (CFB) mode of encryption. Can be applied for any block encryption algorithm
  351.  * with any block size, such as the DES or the IDEA cipher.  */
  352.  
  353. static void cfbshift(iv, buf,  count, blocksize)
  354.     register byteptr iv; register byteptr buf;
  355.     register int count; int blocksize;
  356. /* iv is initialization vector. buf is buffer pointer. count is number of bytes
  357.  * to shift in...must be > 0. blocksize is 8 bytes for DES or IDEA ciphers. */
  358. {
  359.        int retained;
  360.        if (count)
  361.        {
  362.          retained = blocksize-count;   /* number bytes in iv to retain */
  363.      /* left-shift retained bytes of IV over by count bytes to make room */
  364.          while (retained--)
  365.          {
  366.             *iv = *(iv+count);
  367.             iv++;
  368.          }
  369.          /* now copy count bytes from buf to shifted tail of IV */
  370.          do     *iv++ = *buf++;
  371.          while (--count);
  372.        }
  373. }      /* cfbshift */
  374.  
  375. /* Key schedules for IDEA encryption and decryption */
  376.  
  377. static IDEAkey Z, DK;
  378. static word16 *iv_idea;        /* pointer to IV for CFB or CBC */
  379. static boolean cfb_dc_idea;    /* TRUE iff CFB decrypting */
  380.  
  381. /* initkey_idea initializes IDEA for ECB mode operations */
  382.  
  383. void initkey_idea(key, decryp)
  384.     byte key[16]; boolean decryp;
  385. {
  386.        word16 userkey[8]; /* IDEA key is 16 bytes long */
  387.        int i;
  388.        /* Assume each pair of bytes comprising a word is ordered MSB-first. */
  389.        for (i=0; i<8; i++)
  390.        {
  391.          userkey[i] = (key[0]<<8) + key[1];
  392.          key++; key++;
  393.        }
  394.        en_key_idea(userkey,Z);
  395.        if (decryp)
  396.        {
  397.          de_key_idea(Z,Z);     /* compute inverse key schedule DK */
  398.        }
  399.        for (i=0; i<8; i++)/* Erase dangerous traces */
  400.          userkey[i] = 0;
  401. } /* initkey_idea */
  402.  
  403. /* Run a 64-bit block thru IDEA in ECB (Electronic Code Book) mode, using the
  404.  * currently selected key schedule. */
  405.  
  406. void idea_ecb(inbuf, outbuf)
  407.     word16 *inbuf; word16 *outbuf;
  408. {
  409.        /* Assume each pair of bytes comprising a word is ordered MSB-first. */
  410. #ifndef HIGHFIRST   /* If this is a least-significant-byte-first CPU */
  411.        word16 x;
  412.        /* Invert the byte order for each 16-bit word for internal use. */
  413.        x = inbuf[0]; outbuf[0] = x >> 8 | x << 8;
  414.        x = inbuf[1]; outbuf[1] = x >> 8 | x << 8;
  415.        x = inbuf[2]; outbuf[2] = x >> 8 | x << 8;
  416.        x = inbuf[3]; outbuf[3] = x >> 8 | x << 8;
  417.        cipher_idea(outbuf, outbuf, Z);
  418.        x = outbuf[0]; outbuf[0] = x >> 8 | x << 8;
  419.        x = outbuf[1]; outbuf[1] = x >> 8 | x << 8;
  420.        x = outbuf[2]; outbuf[2] = x >> 8 | x << 8;
  421.        x = outbuf[3]; outbuf[3] = x >> 8 | x << 8;
  422. #else  /* HIGHFIRST */
  423.        /* Byte order for internal and external representations is the same. */
  424.        cipher_idea(inbuf, outbuf, Z);
  425. #endif /* HIGHFIRST */
  426. } /* idea_ecb */
  427.  
  428. /* initcfb - Initializes IDEA key schedule tables via key; initializes Cipher
  429.  * Feedback mode IV. References context variables cfb_dc_idea and iv_idea.  */
  430.  
  431. void initcfb_idea(iv0, key, decryp)
  432.     word16 iv0[4]; byte key[16]; boolean decryp;
  433. /* iv0 is copied to global iv_idea, buffer will be destroyed by ideacfb. key is
  434.  * pointer to key buffer. decryp is TRUE if decrypting, FALSE if encrypting. */
  435. {
  436.        iv_idea = iv0;
  437.        cfb_dc_idea = decryp;
  438.        initkey_idea(key,FALSE);
  439. }
  440.  
  441. /* ideacfb - encipher a buffer with IDEA enciphering algorithm, using Cipher
  442.  *  Feedback (CFB) mode. Assumes initcfb_idea has already been called. 
  443.  * References context variables cfb_dc_idea and iv_idea.  */
  444.  
  445. void ideacfb(buf, count)
  446.     byteptr buf; int count;
  447. /* buf is input, output buffer, may be more than 1 block. count is byte count
  448.  * is byte count of buffer.  May be > IDEABLOCKSIZE. */
  449. {
  450.        int chunksize;             /* smaller of count, IDEABLOCKSIZE */
  451.        word16 temp[IDEABLOCKSIZE/2];
  452.  
  453.        while ((chunksize = min(count,IDEABLOCKSIZE)) > 0)
  454.        {
  455.          idea_ecb(iv_idea,temp);  /* encrypt iv_idea, making temp. */ 
  456.          if (cfb_dc_idea)/* buf is ciphertext */
  457.             /* shift in ciphertext to IV... */
  458.             cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
  459.          /* convert buf via xor */
  460.          xorbuf(buf,(byte *)temp,chunksize);/* buf has enciphered output */
  461.          if (!cfb_dc_idea)/* buf was plaintext, is now ciphertext */
  462.             /* shift in ciphertext to IV... */
  463.             cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
  464.          count -= chunksize;
  465.          buf += chunksize;
  466.        }
  467. }
  468.  
  469. /* close_idea function erases all the key schedule information when we are 
  470.  * done with a set of operations for a particular IDEA key context. This is to
  471.  * prevent any sensitive data from being left around in memory. */
  472.  
  473. void close_idea()      /* erase current key schedule tables */
  474. {
  475.        short i;
  476.        for (i = 0; i < KEYLEN; i++)
  477.          Z[i] = 0;
  478. }      /* close_idea() */
  479.  
  480. /* These buffers are used by init_idearand, idearand, and close_idearand. */
  481. static word16 dtbuf_idea[4] = {0};     /* buffer for enciphered timestamp */
  482. static word16 randseed_idea[4] = {0};  /* seed for IDEA random # generator */
  483. static word16 randbuf_idea[4] = {0};   /* buffer for IDEA random # generator */
  484. static byte randbuf_idea_counter = 0;  /* random bytes left in randbuf_idea */
  485.  
  486. /* init_idearand - initialize idearand, IDEA random number generator. Used for
  487.  *  generating cryptographically strong random numbers. Much of design comes 
  488.  * from Appendix C of ANSI X9.17. key is pointer to IDEA key buffer. seed is 
  489.  * pointer to random number seed buffer. tstamp is a 32-bit timestamp */
  490.  
  491. void init_idearand(key, seed, tstamp)
  492.     byte key[16]; byte seed[8]; word32 tstamp;
  493. {
  494.        int i;
  495.        initkey_idea(key, FALSE);      /* initialize IDEA */
  496.        for (i=0; i<4; i++)          /* capture timestamp material */
  497.        {     dtbuf_idea[i] = tstamp;  /* get bottom word */
  498.          tstamp = tstamp >> 16;   /* drop bottom word */
  499.          /* tstamp has only 4 bytes-- last 4 bytes will always be 0 */
  500.        }
  501.        /* Start with enciphered timestamp: */
  502.        idea_ecb(dtbuf_idea,dtbuf_idea);
  503.        /* initialize seed material */
  504.        for (i=0; i<8; i++)
  505.          ((byte *)randseed_idea)[i] = seed[i];
  506.        randbuf_idea_counter = 0; /* # of random bytes left in randbuf_idea */
  507. }
  508.  
  509. /* idearand - IDEA pseudo-random number generator. Used for generating 
  510.  * cryptographically strong random numbers. Much of design comes from Appendix
  511.  * C of ANSI X9.17.  */
  512.  
  513. byte idearand()
  514. {
  515.        int i;
  516.        if (randbuf_idea_counter==0)        /* if random buffer is spent...*/
  517.        {     /* Combine enciphered timestamp with seed material: */
  518.          for (i=0; i<4; i++)
  519.             randseed_idea[i] ^= dtbuf_idea[i];
  520.          idea_ecb(randseed_idea,randbuf_idea);   /* fill new block */
  521.          /* Compute new seed vector: */
  522.          for (i=0; i<4; i++)
  523.             randseed_idea[i] = randbuf_idea[i] ^ dtbuf_idea[i];
  524.          idea_ecb(randseed_idea,randseed_idea);    /* fill new seed */
  525.          randbuf_idea_counter = 8;     /* reset counter for full buffer */
  526.        }
  527.        /* Take a byte from randbuf_idea: */
  528.        return(((byte *)randbuf_idea)[--randbuf_idea_counter]);
  529. }
  530.  
  531. void close_idearand()
  532. {      /* Erase random IDEA buffers and wipe out IDEA key info */
  533.        int i;
  534.        for (i=0; i<4; i++)
  535.        {     randbuf_idea[i] = 0;
  536.          randseed_idea[i] = 0;
  537.          dtbuf_idea[i] = 0;
  538.        }
  539.        close_idea();/* erase current key schedule tables */
  540. }
  541.